package com.atguigu.algorithm.search;

import java.util.Arrays;

/**
 * 斐波那契（黄金分割法）查找
 * 思路同二分查找法，mid的计算公式不同 mid = low+F(k-1)-1
 *
 * @author xr-8
 * @date 2022-09-12
 * @time 23:56
 */
public class FibonacciSearch {

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        System.out.println(search(arr, 10));
    }

    public static int search(int[] arr, int num) {
        // 1、获取斐波那契数列
        int[] fib = fib();
        // 2、得到数组对应的大概的斐波那契数列下标
        int k = 0;
        while (arr.length > fib[k]) {
            k++;
        }
        // 3、扩充数组长度成斐波那契数
        int[] newArr = Arrays.copyOf(arr, fib[k]);
        for (int i = arr.length - 1; i < newArr.length; i++) {
            newArr[i] = arr[arr.length - 1];
        }
        System.out.println("newArr=" + Arrays.toString(newArr));
        // 4、开始查找,关键点在于公式中k的数值
        int left = 0;
        int right = arr.length - 1;
        int mid;
        while (left <= right) {
            mid = left + fib[k - 1] - 1;
            if (newArr[mid] > num) {
                right = mid - 1;
                //为甚是 k--
                //说明
                //1. 全部元素 = 前面的元素 + 后边元素
                //2. f[k] = f[k-1] + f[k-2]
                //因为 前面有 f[k-1]个元素,所以可以继续拆分 f[k-1] = f[k-2] + f[k-3]
                //即 在 f[k-1] 的前面继续查找 k--
                //即下次循环 mid = f[k-1-1]-1
                k--;
            } else if (newArr[mid] < num) {
                left = mid + 1;
                //为什么是k -=2
                //说明
                //1. 全部元素 = 前面的元素 + 后边元素
                //2. f[k] = f[k-1] + f[k-2]
                //3. 因为后面我们有f[k-2] 所以可以继续拆分 f[k-1] = f[k-3] + f[k-4]
                //4. 即在f[k-2] 的前面进行查找 k -=2
                //5. 即下次循环 mid = f[k - 1 - 2] - 1
                k -= 2;
            } else {
                //需要返回的是原arr的下标，超出原arr长度的下标，按right处理
                if (mid <= right) {
                    return mid;
                } else {
                    return right;
                }
            }
        }
        return -1;
    }

    /**
     * 生成斐波那契数列
     *
     * @return
     */
    public static int[] fib() {
        int[] fib = new int[20];
        fib[0] = 1;
        fib[1] = 1;
        for (int i = 2; i < fib.length; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
        System.out.println("fib=" + Arrays.toString(fib));
        return fib;
    }
}
